/*-------------------------------------------------------------------------
 *
 * pg_bitutils.h
 *	  位运算的杂项函数。
 *
 *
 * Copyright (c) 2019-2022, PostgreSQL Global Development Group
 *
 * src/include/port/pg_bitutils.h
 *
 *-------------------------------------------------------------------------
 */
#ifndef PG_BITUTILS_H
#define PG_BITUTILS_H

extern PGDLLIMPORT const uint8 pg_leftmost_one_pos[256];
extern PGDLLIMPORT const uint8 pg_rightmost_one_pos[256];
extern PGDLLIMPORT const uint8 pg_number_of_ones[256];

/*
 * pg_leftmost_one_pos32
 *		返回“word”中最重要的设置位的位置，
 *		从最低有效位开始计量。word不能为0。
 */
static inline int
pg_leftmost_one_pos32(uint32 word)
{
#ifdef HAVE__BUILTIN_CLZ
	Assert(word != 0);

	return 31 - __builtin_clz(word);
#else
	int			shift = 32 - 8;

	Assert(word != 0);

	while ((word >> shift) == 0)
		shift -= 8;

	return shift + pg_leftmost_one_pos[(word >> shift) & 255];
#endif							/* HAVE__BUILTIN_CLZ */
}

/*
 * pg_leftmost_one_pos64
 *		同上，但用于64位字。
 */
static inline int
pg_leftmost_one_pos64(uint64 word)
{
#ifdef HAVE__BUILTIN_CLZ
	Assert(word != 0);

#if defined(HAVE_LONG_INT_64)
	return 63 - __builtin_clzl(word);
#elif defined(HAVE_LONG_LONG_INT_64)
	return 63 - __builtin_clzll(word);
#else
#error must have a working 64-bit integer datatype
#endif
#else							/* !HAVE__BUILTIN_CLZ */
	int			shift = 64 - 8;

	Assert(word != 0);

	while ((word >> shift) == 0)
		shift -= 8;

	return shift + pg_leftmost_one_pos[(word >> shift) & 255];
#endif							/* HAVE__BUILTIN_CLZ */
}

/*
 * pg_rightmost_one_pos32
 *		返回“word”中最低有效的设置位的位置，
 *		从最低有效位开始计量。word不能为0。
 */
static inline int
pg_rightmost_one_pos32(uint32 word)
{
#ifdef HAVE__BUILTIN_CTZ
	Assert(word != 0);

	return __builtin_ctz(word);
#else
	int			result = 0;

	Assert(word != 0);

	while ((word & 255) == 0)
	{
		word >>= 8;
		result += 8;
	}
	result += pg_rightmost_one_pos[word & 255];
	return result;
#endif							/* HAVE__BUILTIN_CTZ */
}

/*
 * pg_rightmost_one_pos64
 *		与上面相同，但用于64位字。
 */
static inline int
pg_rightmost_one_pos64(uint64 word)
{
#ifdef HAVE__BUILTIN_CTZ
	Assert(word != 0);

#if defined(HAVE_LONG_INT_64)
	return __builtin_ctzl(word);
#elif defined(HAVE_LONG_LONG_INT_64)
	return __builtin_ctzll(word);
#else
#error must have a working 64-bit integer datatype
#endif
#else							/* !HAVE__BUILTIN_CTZ */
	int			result = 0;

	Assert(word != 0);

	while ((word & 255) == 0)
	{
		word >>= 8;
		result += 8;
	}
	result += pg_rightmost_one_pos[word & 255];
	return result;
#endif							/* HAVE__BUILTIN_CTZ */
}

/*
 * pg_nextpower2_32
 *		返回“num”之上下一个更高的2的幂，如果“num”
 *		已经是2的幂，则返回“num”。
 *
 * “num”不能为0或超过PG_UINT32_MAX / 2 + 1。
 */
static inline uint32
pg_nextpower2_32(uint32 num)
{
	Assert(num > 0 && num <= PG_UINT32_MAX / 2 + 1);

	/*
	 * 2的幂数只有1个位被设置。从这样的数字中减去1
	 * 将开启所有先前的位，从而导致num和num-1之间没有
	 * 共同的位被设置。
	 */
	if ((num & (num - 1)) == 0)
		return num;				/* 已经是2的幂 */

	return ((uint32) 1) << (pg_leftmost_one_pos32(num) + 1);
}

/*
 * pg_nextpower2_64
 *		返回“num”之上下一个更高的2的幂，如果“num”
 *		已经是2的幂，则返回“num”。
 *
 * “num”不能为0或超过PG_UINT64_MAX / 2 + 1。
 */
static inline uint64
pg_nextpower2_64(uint64 num)
{
	Assert(num > 0 && num <= PG_UINT64_MAX / 2 + 1);

	/*
	 * 2的幂数只有1个位被设置。从这样的数字中减去1
	 * 将开启所有先前的位，从而导致num和num-1之间没有
	 * 共同的位被设置。
	 */
	if ((num & (num - 1)) == 0)
		return num;				/* 已经是2的幂 */

	return ((uint64) 1) << (pg_leftmost_one_pos64(num) + 1);
}

/*
 * pg_nextpower2_size_t
 *		返回“num”之上更高的2的幂，适用于size_t输入。
 */
#if SIZEOF_SIZE_T == 4
#define pg_nextpower2_size_t(num) pg_nextpower2_32(num)
#else
#define pg_nextpower2_size_t(num) pg_nextpower2_64(num)
#endif

/*
 * pg_prevpower2_32
 *		返回“num”之下下一个更低的2的幂，如果“num”
 *		已经是2的幂，则返回“num”。
 *
 * “num”不能为0。
 */
static inline uint32
pg_prevpower2_32(uint32 num)
{
	return ((uint32) 1) << pg_leftmost_one_pos32(num);
}

/*
 * pg_prevpower2_64
 *		返回“num”之下下一个更低的2的幂，如果“num”
 *		已经是2的幂，则返回“num”。
 *
 * “num”不能为0。
 */
static inline uint64
pg_prevpower2_64(uint64 num)
{
	return ((uint64) 1) << pg_leftmost_one_pos64(num);
}

/*
 * pg_prevpower2_size_t
 *		返回小于 'num' 的下一个较低的 2 的幂，适用于 size_t 输入。
 */
#if SIZEOF_SIZE_T == 4
#define pg_prevpower2_size_t(num) pg_prevpower2_32(num)
#else
#define pg_prevpower2_size_t(num) pg_prevpower2_64(num)
#endif

/*
 * pg_ceil_log2_32
 *		返回 ceil(log2(num)) 的等效值
 */
static inline uint32
pg_ceil_log2_32(uint32 num)
{
	if (num < 2)
		return 0;
	else
		return pg_leftmost_one_pos32(num - 1) + 1;
}

/*
 * pg_ceil_log2_64
 *		返回 ceil(log2(num)) 的等效值
 */
static inline uint64
pg_ceil_log2_64(uint64 num)
{
	if (num < 2)
		return 0;
	else
		return pg_leftmost_one_pos64(num - 1) + 1;
}

/*
 * 在 x86_64 构建的 MSVC 上，尝试通过 __popcnt 和 __popcnt64 内置函数来使用本地 popcnt 指令。
 * 这些指令与 GCC 的 __builtin_popcount* 内置函数的工作原理不同，因为它们始终会发出 popcnt 指令。
 */
#if defined(_MSC_VER) && defined(_M_AMD64)
#define HAVE_X86_64_POPCNTQ
#endif

/*
 * 在 x86_64 上，我们可以使用硬件 popcount 指令，但前提是我们能够通过 cpuid 指令验证 CPU 是否支持它。
 *
 * 否则，我们将回退到手动实现。
 */
#ifdef HAVE_X86_64_POPCNTQ
#if defined(HAVE__GET_CPUID) || defined(HAVE__CPUID)
#define TRY_POPCNT_FAST 1
#endif
#endif

#ifdef TRY_POPCNT_FAST
/* 尝试使用 POPCNT 指令，但先进行运行时检查 */
extern int	(*pg_popcount32) (uint32 word);
extern int	(*pg_popcount64) (uint64 word);

#else
/* 使用可移植的实现 -- 不需要函数指针。 */
extern int	pg_popcount32(uint32 word);
extern int	pg_popcount64(uint64 word);

#endif							/* 尝试快速POPcnt */

/* 计算字节数组中 1 位的个数 */
extern uint64 pg_popcount(const char *buf, int bytes);

/*
 * 将 "word" 的位向右/左旋转 n 位。
 */
static inline uint32
pg_rotate_right32(uint32 word, int n)
{
	return (word >> n) | (word << (32 - n));
}

static inline uint32
pg_rotate_left32(uint32 word, int n)
{
	return (word << n) | (word >> (32 - n));
}

#endif							/* PG_BITUTILS_H */
